
# a = input("请输入第一个数字")
# b = input("请输入第二个数字")
# c = input("请输入第三个数字")
# a = float(a)
# b = float(b)
# c = float(c)
# avg = (a + b + c) / 3
# print(f"平均值为:{avg}")

# def add(start, end):
#     ret_sum = 0
#     for i in range (start, end + 1):
#         ret_sum += i
#     return ret_sum
#
# print(f"1～100的和为:{add(1, 100)}")

# 冒泡
# def bubble_sort(arr):
#     for i in range(0, len(arr) - 1):
#         for j in range(0, len(arr) - i - 1):
#             if arr[j] > arr[j + 1]:
#                 tmp = arr[j]
#                 arr[j] = arr[j + 1]
#                 arr[j + 1] = tmp
#
#
# arr = [3, 1, 5, 9, 1, 2]
# bubble_sort(arr)
# 遍历
def print_arr(arr):
    for i in arr:
        print(i, end=' ')

# 交换
def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

# 插入排序
def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        for j in range(i - 1 , -1, -1):
            if arr[j] > key:
                arr[j + 1] = arr[j]
            else:
                break
        arr[j] = key

# arr = [3,1,4,2,6,9,8,7,5]
arr = [3, 1, 4, 2]
insert_sort(arr)
print_arr(arr)


class Solution(object):
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1



